﻿using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.IO;

public class GraphBuilder {

    private string[,] tiles = new string[DataStorage.Instance.GetMapWidth(), DataStorage.Instance.GetMapHeight()];

    List<Edge> edges = new List<Edge>();

    private int roomCounter = 0;

    private bool temp = false;

    public void CreateGraph()
    {
        List<Room> rooms = DataStorage.Instance.GetRoomList();
        List<Room> neighbourRooms = new List<Room>(); //list for neighboured rooms, that gets cleared after every loop
        edges = new List<Edge>();
        foreach (Room roomA in rooms)
        {
            roomCounter++;
            foreach (Room roomB in rooms) 
            {
                if (roomA.IsNeighbour(roomB)) 
                    neighbourRooms.Add(roomB); //find the neighbours of the room
            }
            foreach (Room neighbourRoom in neighbourRooms)
            {
                FindPath(roomA, neighbourRoom); //Find the paths from roomA to all the neighboured rooms
            }
            neighbourRooms.Clear();
        }
    }

    private bool FindPath(Room start, Room neighbourRoom)
    {
        Edge edge = new Edge(start, neighbourRoom);
        //List<Edge> edgeList = DataStorage.Instance.GetEdgeList();
        foreach(Edge edgeInList in edges) //if an edge has already been assessed and added, don't do it again, you dirty hack
        {
            if (edge.Equals(edgeInList))
            {
                return true;
            }
        }
        tiles = (string[,])MapOverview.Instance.GetTileMap().Clone();

        for (int x = neighbourRoom.GetXLeft(); x <= neighbourRoom.GetXRight(); x++)
        {
            for (int y = neighbourRoom.GetYTop(); y >= neighbourRoom.GetYBottom(); y--)
            {
                    tiles[x, y] = "0";
            }
        }
        tiles[neighbourRoom.GetXLeft(), neighbourRoom.GetYBottom()] = "w";
        tiles[neighbourRoom.GetXLeft(), neighbourRoom.GetYTop()] = "w";
        tiles[neighbourRoom.GetXRight(), neighbourRoom.GetYBottom()] = "w";
        tiles[neighbourRoom.GetXRight(), neighbourRoom.GetYTop()] = "w";

        List<Point> openList = new List<Point>(); //Step 1
        List<Point> closedList = new List<Point>();
        openList.Add(start.GetCenter());
        while (true)
        {
            if (openList.Count == 0) //Step 2
                return false;

            Point n = null; //the score is the lowest manhattan distance for a point in openList
            int bestScore = int.MaxValue;
            foreach (Point openElement in openList) //Step 3
            {
                if (openElement.score == -1)
                    openElement.SetScore(CalcManhattanDistance(openElement, neighbourRoom.GetCenter()));
                if (openElement.score < bestScore)
                {
                    bestScore = openElement.score;
                    n = openElement;
                }
            }

            openList.Remove(n);
            closedList.Add(n);

            List<Point> successors = new List<Point>(); //Step 4
            if (n.x >= 0 && n.x < DataStorage.Instance.GetMapWidth() && n.y - 1 >= 0 && n.y - 1 < DataStorage.Instance.GetMapHeight()
            && tiles[n.x, n.y - 1] == "0")
                successors.Add(new Point(n.x, n.y - 1)); //north
            if (n.x + 1 >= 0 && n.x + 1 < DataStorage.Instance.GetMapWidth() && n.y >= 0 && n.y < DataStorage.Instance.GetMapHeight()
            && tiles[n.x + 1, n.y] == "0")
                successors.Add(new Point(n.x + 1, n.y)); //east
            if (n.x >= 0 && n.x < DataStorage.Instance.GetMapWidth() && n.y + 1 >= 0 && n.y + 1 < DataStorage.Instance.GetMapHeight()
            && tiles[n.x, n.y + 1] == "0")
                successors.Add(new Point(n.x, n.y + 1)); //south
            if (n.x - 1 >= 0 && n.x - 1 < DataStorage.Instance.GetMapWidth() && n.y >= 0 && n.y < DataStorage.Instance.GetMapHeight()
            && tiles[n.x - 1, n.y] == "0")
                successors.Add(new Point(n.x - 1, n.y)); //west

            foreach (Point successor in successors) 
            {
                if (successor.Equals(neighbourRoom.GetCenter())) //Step 5
                {
                    closedList.Add(successor);
                    edge.SetRoute(closedList);
                    edges.Add(edge);
                    DataStorage.Instance.SetEdgeList(edges);
                    //MapOverview.Instance.MarkMapAsUsed(neighbourRoom.GetXLeft(), neighbourRoom.GetYTop(), neighbourRoom.GetXLeft() + neighbourRoom.GetWidth() - 1, neighbourRoom.GetYTop() - neighbourRoom.GetHeight() + 1);
                    //MapOverview.Instance.DeleteUnnecessary();
                    return true;
                }
                else
                    successor.SetScore(CalcManhattanDistance(successor, neighbourRoom.GetCenter())); //Step 6
            }


            foreach (Point successor in successors)
            {
                bool alreadyAdded = false;
                foreach (Point openElement in openList)
                {
                    if (openElement.Equals(successor))
                        alreadyAdded = true;
                }
                if (!alreadyAdded)
                    openList.Add(successor);
            }
        }
    }

    private int CalcManhattanDistance(Point point, Point dest)
    {
        return Mathf.Abs(point.x - dest.x) + Mathf.Abs(point.y - dest.y);
    }

    public void SelectEdges()
    {
        edges = DataStorage.Instance.GetEdgeList();
        List<Edge> edgesUsed = new List<Edge>();

        //TODO: Sorting the edges

        //foreach (Edge edgeOuter in edges)
        //{
        //    edgesSorted.Add(edgeOuter);
        //    foreach (Edge edgeInner in edges)
        //    {
        //        if (edgesSorted[edgesSorted.Count - 1].Length > edgeInner.Length)
        //            edgesSorted[edgesSorted.Count - 1] = edgeInner;
        //    }

        //}

        //for (int i=0; i < edges.Count; i++)
        //{
        //    edgesSorted.Add(edges[i]);
        //    for (int j=0; j < edges.Count; j++)
        //    {
        //        if (edgesSorted[edgesSorted.Count - 1].Length > edges[j].Length)
        //            edgesSorted[edgesSorted.Count - 1] = edges[j];
        //    }
        //    edges.Remove(edgesSorted[edgesSorted.Count - 1]);

        //}
        while (edges.Count > 0)
        {
            for (int i = 0; i < edges.Count; i++)
            {
                edgesUsed.Add(edges[i]);
                if (IsCycle(edgesUsed)) //IsCycle may only be used with new edges. If an edge, that has already been evaluated, is used with IsCycle, it's always true
                {
                    Edge edgeTemp = edgesUsed[edgesUsed.Count - 1];
                    edgesUsed.Remove(edgeTemp);
                    edges.Remove(edgeTemp);

                }
                else
                {
                    Edge edgeTemp = edgesUsed[edgesUsed.Count - 1];
                    edges.Remove(edgeTemp);
                }

            }
        }
        DataStorage.Instance.SetUsedEdgeList(edges); 
        DataStorage.Instance.SetUsedEdgeList(edgesUsed);
        //MapOverview.Instance.UpdateMapWithRoutes();
        //MapOverview.Instance.InsertCorners();
        //MapOverview.Instance.PrintMap();


    }

    private bool IsCycle(List<Edge> _edgesUsed)
    {
        Point pointA = Find(_edgesUsed[_edgesUsed.Count - 1].pointA);
        Point pointB = Find(_edgesUsed[_edgesUsed.Count - 1].pointB);

        if (pointA.Equals(pointB))
            return true;

        Union(pointA, pointB);

        return false;
    }

    private void Union(Point pointA, Point pointB)
    {
        Point aSet = Find(pointA);
        Point bSet = Find(pointB);
        bSet.parent = aSet;
    }

    private Point Find(Point point)
    {
        if (point.parent==null)
            return point;
        return Find(point.parent);
    }
}
